package org.aplombh.java.awcing.basic.graph.graphTraversal.dfs;


import java.util.Scanner;

/**
 * 给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
 * <p>
 * 现在，请你按照字典序将所有的排列方法输出。
 * <p>
 * 输入格式
 * 共一行，包含一个整数 n。
 * <p>
 * 输出格式
 * 按字典序输出所有排列方案，每个方案占一行。
 * <p>
 * 数据范围
 * 1≤n≤7
 * 输入样例：
 * 3
 * 输出样例：
 * 1 2 3
 * 1 3 2
 * 2 1 3
 * 2 3 1
 * 3 1 2
 * 3 2 1
 */
public class ArrangementOfDigital_842 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrangementOfDigital arrangementOfDigital = new ArrangementOfDigital(n);
        arrangementOfDigital.dfs(0);
    }
}

class ArrangementOfDigital {

    static final int N = 10000010;   // 最大长度
    int n;  // 总长度
    int[] path; // 存储路径 storage path
    boolean[] st; // 标记该数字是否被使用过 Marks whether a number has been used

    // 初始化
    ArrangementOfDigital(int n) {
        this.n = n;
        path = new int[N];
        st = new boolean[N];
    }


    void dfs(int u) {

        // 如果遍历到最后一位，输出
        if (u == n) {
            // 输出该路径 Output the path
            for (int i = 0; i < n; i++) System.out.print(path[i] + " ");
            System.out.println();
            return;
        }

        // 遍历所有节点
        for (int i = 1; i <= n; i++) {
            // 找到未使用的节点 Find unused nodes
            if (!st[i]) {

                // 存储当前路径的节点 Stores the current path node
                // 存储当前节点
                // u为要遍历的第几个节点
                path[u] = i;

                // 标记当前节点已被使用 Mark the node is in use
                st[i] = true;

                // 遍历下一个节点
                dfs(u + 1);

                // 去除标记 Remove the mark
                st[i] = false;
            }
        }
    }
}
